"""
quicksort
三向切分快速排序（快排实验v4_1）
"""
import random


def rand_partition(sequence, p, r, key):
    i = random.randint(p, r)
    sequence[p], sequence[i] = sequence[i], sequence[p]
    x = key(sequence[p])
    lt = p
    gt = r
    i = p + 1
    while i <= gt:
        key_i = key(sequence[i])
        if key_i < x:
            sequence[lt], sequence[i] = sequence[i], sequence[lt]
            lt += 1
            i += 1
        elif key_i == x:
            i += 1
        else:
            while key(sequence[gt]) > x and i <= gt:
                gt -= 1
            if i < gt:
                sequence[i], sequence[gt] = sequence[gt], sequence[i]
                gt -= 1

    return lt, gt


def _quicksort(sequence, p, r, key):
    if p < r:
        lt, gt = rand_partition(sequence, p, r, key)
        _quicksort(sequence, p, lt - 1, key)
        _quicksort(sequence, gt + 1, r, key)


def quicksort(sequence, key=None):
    if key is None:
        def default_key(x):
            return x
        key = default_key
    _quicksort(sequence, 0, len(sequence) - 1, key)


if __name__ == '__main__':
    import os
    import time

    # s = list(range(100))
    # s = [7, 8, 9, 5, 1, 4, 2, 3, 6, 0]
    # random.shuffle(s)
    s = random.choices(range(100), k=100)
    print('s:', s)
    start = time.time()
    quicksort(s, key=lambda x: -x)
    elapsed = time.time() - start
    print('sorted s:', s)
    print('sort success')
    print('consume:', elapsed)

